Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D - Immutable - 图1

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

  1. Given matrix = [
  2.   [3, 0, 1, 4, 2],
  3.   [5, 6, 3, 2, 1],
  4.   [1, 2, 0, 1, 5],
  5.   [4, 1, 0, 1, 7],
  6.   [1, 0, 3, 0, 5]
  7. ]
  9. sumRegion(2, 1, 4, 3) -> 8
  10. sumRegion(1, 1, 2, 2) -> 11
  11. sumRegion(1, 2, 2, 4) -> 12

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Solution:

  1. public class NumMatrix {
  2.   int[][] sum;
  4.   public NumMatrix(int[][] matrix) {
  5.     if (matrix.length == 0 || matrix[0].length == 0) {
  6.       return;
  7.     }
  9.     int m = matrix.length, n = matrix[0].length;
  11.     sum = new int[m+1][n+1];
  13.     for (int i = 1; i <= m; i++) {
  14.       for (int j = 1; j <= n; j++) {
  15.         sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
  16.       }
  17.     }
  18.   }
  20.   public int sumRegion(int row1, int col1, int row2, int col2) {
  21.     return sum[row2+1][col2+1] - sum[row2+1][col1] - sum[row1][col2+1] + sum[row1][col1];
  22.   }
  23. }
  26. // Your NumMatrix object will be instantiated and called as such:
  27. // NumMatrix numMatrix = new NumMatrix(matrix);
  28. // numMatrix.sumRegion(0, 1, 2, 3);
  29. // numMatrix.sumRegion(1, 2, 3, 4);